๋ฌธ์
'Dummy' ๋ผ๋ ๋์ค๊ฒ์์ด ์๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค.
๊ฒ์์ NxN ์ ์ฌ๊ฐ ๋ณด๋์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋ณด๋์ ์ํ์ข์ฐ ๋์ ๋ฒฝ์ด ์๋ค. ๊ฒ์์ด ์์ํ ๋ ๋ฑ์ ๋งจ์ ๋งจ์ข์ธก์ ์์นํ๊ณ ๋ฑ์ ๊ธธ์ด๋ 1 ์ด๋ค. ๋ฑ์ ์ฒ์์ ์ค๋ฅธ์ชฝ์ ํฅํ๋ค.
๋ฑ์ ๋งค ์ด๋ง๋ค ์ด๋์ ํ๋๋ฐ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ฅธ๋ค.
- ๋จผ์ ๋ฑ์ ๋ชธ๊ธธ์ด๋ฅผ ๋๋ ค ๋จธ๋ฆฌ๋ฅผ ๋ค์์นธ์ ์์น์ํจ๋ค.
- ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๊ทธ ์นธ์ ์๋ ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์๋๋ค.
- ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์์ค๋ค. ์ฆ, ๋ชธ๊ธธ์ด๋ ๋ณํ์ง ์๋๋ค.
์ฌ๊ณผ์ ์์น์ ๋ฑ์ ์ด๋๊ฒฝ๋ก๊ฐ ์ฃผ์ด์ง ๋ ์ด ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ๊ณ์ฐํ๋ผ.
์ , ์ถ๋ ฅ
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๋ค. (2 โค N โค 100) ๋ค์ ์ค์ ์ฌ๊ณผ์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค. (0 โค K โค 100)
- ๋ค์ K๊ฐ์ ์ค์๋ ์ฌ๊ณผ์ ์์น๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฒซ ๋ฒ์งธ ์ ์๋ ํ, ๋ ๋ฒ์งธ ์ ์๋ ์ด ์์น๋ฅผ ์๋ฏธํ๋ค. ์ฌ๊ณผ์ ์์น๋ ๋ชจ๋ ๋ค๋ฅด๋ฉฐ, ๋งจ ์ ๋งจ ์ข์ธก (1ํ 1์ด) ์๋ ์ฌ๊ณผ๊ฐ ์๋ค.
- ๋ค์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ํ์ L ์ด ์ฃผ์ด์ง๋ค. (1 โค L โค 100)
- ๋ค์ L๊ฐ์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ ์ X์ ๋ฌธ์ C๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ. ๊ฒ์ ์์ ์๊ฐ์ผ๋ก๋ถํฐ X์ด๊ฐ ๋๋ ๋ค์ ์ผ์ชฝ(C๊ฐ 'L') ๋๋ ์ค๋ฅธ์ชฝ(C๊ฐ 'D')๋ก 90๋ ๋ฐฉํฅ์ ํ์ ์ํจ๋ค๋ ๋ป์ด๋ค. X๋ 10,000 ์ดํ์ ์์ ์ ์์ด๋ฉฐ, ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ X๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ์ถ๋ ฅํ๋ค.
๐ Logic
class Info {
int second;
char direction;
public Info (int second, char direction) {
this.second = second;
this.direction = direction;
}
}
- ๋ฑ์ ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ ํด๋์ค
class Dummy {
Info[] infos;
Queue<Pair> queue = new LinkedList<>();
int[][] map;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
int mapSize;
int directionChanges;
int count = 0;
int infoIdx = 0;
int snakeDir;
...
}
- Dummy ๊ฒ์์ ํ์ํ ๋ก์ง์ ๊ตฌํํ๋ ํด๋์ค
map์์ 1์ ๋ฑ์ ์์น, 2๋ ์ฌ๊ณผ์ ์์น๋ฅผ ๋ํ๋ธ๋ค.
private void moveSnake(int x, int y) { ... }
Queue๋ฅผ ์ด์ฉํด์ ๋ฑ์ ๊ผฌ๋ฆฌ ์ ๋ณด๋ฅผ ์ ์ฅํ๊ณ , ํ์์ ๋ฐ๋ผ ๋จผ์ ๋ค์ด์จ ์ขํ๋ฅผ outํ๋ค.- ๋ฑ์ ๋ฐฉํฅ ์ ํ์ ์ํด
snakeDir๋ณ์๋ก ๋ฑ์ ํ์ฌ ๋ฐฉํฅ์ ์ ์ฅํ๋ค. (0, 1, 2, 3 - ๋ถ, ๋, ๋จ, ์) - ์๊ฐ์ ๋ฐ๋ผ
infos์์ ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ฅผ ํ์ธํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class Info {
int second;
char direction;
public Info (int second, char direction) {
this.second = second;
this.direction = direction;
}
}
class Dummy {
Info[] infos;
Queue<Pair> queue = new LinkedList<>();
int[][] map;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
int mapSize;
int directionChanges;
int count = 0;
int infoIdx = 0;
int snakeDir;
public Dummy (int N) {
mapSize = N;
map = new int[N][N];
}
public int game(int directionChanges) {
snakeDir = 1;
this.directionChanges = directionChanges;
moveSnake(0, 0);
return count;
}
private void moveSnake(int x, int y) {
queue.add(new Pair(x, y));
map[x][y] = 1;
if (infoIdx < directionChanges) accessInfo();
x += rangeX[snakeDir];
y += rangeY[snakeDir];
count++;
if (checkBoundary(x, y)) return;
if (map[x][y] == 1) return;
if (map[x][y] != 2) cutTail();
moveSnake(x, y);
}
private void accessInfo() {
if (infos[infoIdx].second == count) {
updateDir();
infoIdx++;
}
}
private void updateDir() {
if (infos[infoIdx].direction == 'L') {
snakeDir = (snakeDir + 3) % 4;
} else {
snakeDir = (snakeDir + 1) % 4;
}
}
private void cutTail() {
if (!queue.isEmpty()) {
Pair out = queue.poll();
map[out.x][out.y] = 0;
}
}
private boolean checkBoundary(int x, int y) {
return (x < 0 || x >= mapSize || y < 0 || y >= mapSize);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Dummy dummy = new Dummy(N);
int appleCount = Integer.parseInt(br.readLine());
String[] line;
for (int i = 0; i < appleCount; i++) {
line = br.readLine().split(" ");
dummy.map[Integer.parseInt(line[0])-1][Integer.parseInt(line[1])-1] = 2;
}
int directionChanges = Integer.parseInt(br.readLine());
dummy.infos = new Info[directionChanges];
for (int i = 0; i < directionChanges; i++) {
line = br.readLine().split(" ");
dummy.infos[i] = new Info(Integer.parseInt(line[0]), line[1].charAt(0));
}
br.close();
System.out.println(dummy.game(directionChanges));
}
}
โ๏ธ Review
- ์น ๋ฐฑ์๋ ๊ธฐ๋ฅ์ ๊ตฌํํ๋ ๊ฒ์ฒ๋ผ, ์๊ตฌ์ฌํญ ํ๋ํ๋์ ํด๋นํ๋ ๊ธฐ๋ฅ ๋ฉ์ด๋ฆฌ๋ฅผ ๋ง๋ค์ด๋ณด์๋ ์๊ฐ์ผ๋ก ์ ๊ทผํ๋ค. ์๋ฎฌ๋ ์ด์ ์ ์ฃผ์ด์ง ๋ก์ง ๊ทธ๋๋ก ๊ตฌํ๋ง ํ๋ฉด ๋๋ ๊ฒ ๊ฐ๋ค.
๐ ์ถ์ฒ
Baekjoon : https://www.acmicpc.net/problem/3190